class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return self.help(nums, k, 0, len(nums)-1)

    # 使数组左边全部大于这个中间数 数组右边全部小于这个中间数
    def help(self, nums, k, left, right):
        mid = nums[left+((right-left)>>1)]
        start = left
        end = right
        while start <= end:
            while start <= end and nums[start] > mid:
                start += 1
            while start <= end and nums[end] < mid:
                end -= 1
            if start <= end:
                temp = nums[start]
                nums[start] = nums[end]
                nums[end] = temp
                start += 1
                end -= 1
        if end-left+1 >= k:
            return self.help(nums, k, left, end)
        elif start-left < k:
            return self.help(nums, k-start+left, start, right)
        return nums[end+1]
